The present invention relates to modeling of integrated circuits, and, more particularly, to the extraction of inductances of the interconnections of integrated circuits for the purpose of simulating such circuits.
In the design of integrated circuits, simulation of circuit function and performance has become an indispensable part of the design process. Simulation is carried out using a computer and simulation software that accepts models of the devices and interconnections of the circuit being simulated. It is obvious that the reliability of the simulation of an integrated circuit depends on the accuracy of the models that are used by the simulation software.
With the design of more densely packed VLSI circuits, the interconnection lines of such circuits have smaller cross sections and are packed closer together. As a result, RC delays of the interconnect wires have become an important limitation on circuit performance, and capacitive coupling between interconnect wires has become a significant source of on-chip noise. In addition, increasing chip densities and switching speeds have imposed a much heavier burden on the power and ground distribution lines to supply sufficient current to switching circuits, and the xcex94I noise caused by heavy transient current demands of switching circuits is becoming a more serious problem.
In an effort to overcome these problems, next generation technologies can be expected to make increasing use of low-resistivity metals, such a copper, and low dielectric constant insulators. Chip designers routinely make power and ground distribution lines using wide, thick upper-level metal and make long signal lines in the same way to reduce resistance. While these improvements reduce RC delays of signal lines and reduce xcex94I noise on power and ground lines, it has now become important to take into account the inductance and inductive coupling of signal lines in simulating the performance of an integrated circuit.
Inductance and inductive coupling have become important in timing and noise analysis of signal lines in several ways. Firstly, inductance must be included in the model of the circuit to accurately predict rise and fall times, as well as delays in timing analysis. Secondly, overdriving an inductive interconnect line can result in an under damped ringing response. Thirdly, inductive coupling, along with capacitive coupling, can be a significant source of noise on a xe2x80x9cquietxe2x80x9d signal line that runs close to another signal line carrying a signal having high frequency components.
Printed circuit board (PCB) and package designers have long been concerned about signal line inductances and return paths for currents in such inductances and typically provide discrete ground and power supply planes to control signal line impedance. Because inductance has not been of concern until recently for on-chip wires in digital VLSI circuits, designers have largely viewed such on-chip signal wires as single-ended distributed RC lines without concern for current returns. Power and ground distribution lines have been designed independently to satisfy power and ground requirements of switching circuits and to minimize the xcex94I noise. When inductance is taken into account in modeling high frequency integrated circuits, the layout of the power and ground distribution lines has an important effect on the response of inductive signal lines in the circuit.
The conventional approach to designing the layout of power and ground distribution lines in a VLSI integrated circuit chip is to create an on-chip grid. Referring to FIG. 1A, there is shown an illustrative cross section of an integrated circuit chip having five levels of conductors designated by M1, M2, M3, M4 and LM. The power and the ground distribution network, which is shown in black, have lines extending in a vertical direction (i.e., parallel to one edge of a rectangular chip) in conductor levels M1, M3 and LM, and lines extending in a horizontal direction (i.e., parallel to the orthogonal edge of the rectangular chip) in conductor levels M2 and M4.
Turning to FIG. 1B, there is shown an illustrative plan view of the power and ground distribution network in the form of a grid. At high frequencies, the power supply and ground are sufficiently decoupled so that the power distribution lines and the ground distribution lines serve equally well in providing return paths for signal line inductances.
Referring to FIG. 1C, there is shown a cross-section view of the design for power and ground distribution used in the Digital Equipment Corporation Alpha 21264 chip, in which two entire metal levels 108 and 109 are dedicated to the distribution of power and ground by providing what amounts to a power plane and a ground plane in a manner conventional to PCB design. Openings are made in these power and ground planes to provide vias for connecting signal lines on opposite sides of the power and ground planes. While the design approach of FIG. 1C provides more control and predictability in signal line, and power and ground line inductances, it is generally considered inefficient usage of the chip metallization levels because wiring resources are always scarce in VLSI circuit chips. Therefore, the grid layout for power and ground distribution, which does not provide well defined return paths for signal line inductances, is the one that is commonly used in high frequency VLSI circuit chips.
To allow equivalent circuits to be developed in complex integrated circuits in which return paths for signal line inductances are not known, the calculation of partial inductances is traditionally used. The partial inductance technique, which assigns portions of a loop inductance to segments along the loop, is described in E. B. Rosa, xe2x80x9cThe Self and Mutual Inductance of Linear Conductors,xe2x80x9d Bulletin of the National Bureau of Standards, 4, pp. 301-344, 1908. A book by F. Grover, entitled xe2x80x9cInductance Calculations: Working Formulas and Tables,xe2x80x9d published by Dover, New York, 1962 provides a comprehensive tabulation of formulae for partial inductances and partial mutual inductances for conductors of different geometries. Applying partial inductances to the modeling of complex multi-conductor networks was formalized by Ruehli with the development of partial-element equivalent circuits (PEEC), as described in A. E. Ruehli, xe2x80x9cInductance Calculations in a Complex Integrated Circuit Environment,xe2x80x9d IBM Journal of Research and Development, 16(5), pp. 470-481, 1972.
In the partial inductance approach, signal lines, power distribution lines and ground distribution lines are treated equivalently, therefore resulting in a very large, densely-coupled inductance matrix representation of the interconnection network. In the partial inductance matrix representation of circuit inductances, a matrix is derived that has as its main diagonal elements the partial self inductances of all signal lines, power distribution lines and ground distribution lines of a circuit, and has as its off-diagonal elements the partial mutual inductances between each one of the signal lines, power distribution lines and ground distribution lines with every other one of such lines in the circuit. Thus an inductance matrix provides a convenient representation of the inductances of a circuit and the elements of the matrix may be used by a circuit simulation program together with circuit resistance and capacitance to model the performance of the circuit. However, the complete inductance matrix of a VLSI circuit derived using the partial inductance technique is so large as to be impractical for use in the simulation of the circuit. Moreover, such a large inductance matrix representing every wire coupled to every other wire in the circuit is not necessary to provide sufficiently accurate circuit simulations.
One approach to make the inductance matrix sparse is to truncate the matrix by discarding those terms that are below a certain threshold. However, truncation does not guarantee that the resulting truncated inductance matrix will be positive semi-definite. An inductance matrix L is positive semi-definite if for an I
ITLIxe2x89xa70,xe2x80x83xe2x80x83(1)
where I is a current vector having as elements the current passing through each signal line, and each power and ground distribution line. The condition of positive semi-definiteness signifies that the magnetostatic energy in the circuit is greater than or equal to zero, a condition which must be met by all physically realizable circuits. Using a truncated non-positive-definite inductance matrix in simulating a circuit will result in instability of the simulation, as described in Zhijiang He, Mustafa Celik, and Lawrence Pileggi, SPIE: xe2x80x9cSparse Partial Inductance Extraction,xe2x80x9d Proceedings of the 34th Design Automation Conference, pp. 137-140, Anaheim, Calif., June 1997.
As an alternative to simple truncation, another proposed technique to render the inductance matrix sparse is to associate with every signal line segment, and every power and ground distribution line segment a distributed current return in the form of a shell located a distance r0 away from the segment. According to this approach, segments spaced more than a distance r0 apart have no inductive coupling. This shell technique is described in B. Krauter and L. T. Pileggi, xe2x80x9cGenerating Sparse Partial Inductance Matrices with Guaranteed Stability,xe2x80x9d Proceedings of the International Conference on Computer-Aided Design, pp. 45-52, 1995. The shell technique has also formed the basis for approximating loop inductance bounds, as described in Zhijiang He and Lawrence T. Pileggi, xe2x80x9cA Simple Algorithm for Calculating Frequency-Dependent Inductance Bounds,xe2x80x9d Proceedings of the IEEE Custom Integrated Circuits Conference, pp. 199-202, 1998.
However, the shell technique has the problem in that the value of r0 that must be used to achieve a desired accuracy depends on the interconnect topology, the connectivity of the interconnect wires in question, and the particular interconnect wire or coupling being considered. There is no way of determining a priori the value of r0 required to achieve tolerable accuracy This leads to complicated schemes in which the value of r0 is dynamically chosen based on accuracy in a particular transfer function calculation, as described in the above-identified reference by Zhijiang He, Mustafa Celik and Lawrence Pileggi. Because r0 is a global parameter, as r0 is adjusted , the entire inductance extraction must be redone. Moreover, the shell technique does not work well for long wires broken into many segments. For a value of r0 sufficiently small to render coupling in the transverse direction sparse, correctly modeling the loop inductances of such long wires may require including mutual inductances between collinear segments more than a distance r0 away.
Accordingly, a need clearly exists for a method for inductance extraction for high frequency integrated circuits, which guarantees a positive semi-definite inductance matrix, while rendering the inductance matrix sparse.
The problems and drawbacks of the prior art, as discussed above, are substantially overcome, and the above-mentioned need is substantially satisfied by the present invention, which is a method for extracting inductances of the interconnection of an integrated circuit which provides a positive semi-definite inductance matrix. The method comprises the steps of first determining the power distribution lines and the ground distribution lines of the integrated circuit. The method further comprises fracturing the signal lines into horizontal and vertical segments, and deriving from the power distribution lines and the ground distribution lines a plurality of disjointed interaction regions, each having a respective section of one or more signal lines, respective sections of two or more of the power distribution lines or the ground distribution lines. The respective sections of the power distribution lines and ground distribution lines in each interaction region are also fractured into vertical and horizontal segments. In each interaction region there is then determined a plurality of coupled loop inductances each defined by a current loop passing through a respective one of the signal line segments in the interaction region and returning through a respective one of the power distribution line segments or a respective one of the ground distribution line segments in the interaction region, the respective one of the power distribution line segments or the respective one of the ground distribution line segments being parallel and adjacent to the respective one of the signal line segments. In addition, the method includes eliminating in each interaction region current loops that do not pass a net current through a signal line segment, and combining in each interaction region the coupled loop inductances into a reduced set of equivalent inductances that model the inductance of each signal line section in the interaction region.
Thus the inductance matrix of the circuit chip is rendered sparse in two important ways: (1) the inductances of the power distribution lines and the ground distribution lines are extracted independently of the signal lines, and therefore, there is no mutual coupling between power and ground distribution lines, and signal lines; and (2) mutual inductances between signal lines are further restricted by set of simple geometry-based decomposition rules, which are referred to as halo rules, for defining the plurality of disjointed interaction regions.